fn fib_dp(n: u32) -> u32 {  
    let n = n as usize;
    let mut dp = vec![0; (n+1) as usize];  
    // TODO: 填充 dp 表  
    dp[0] = 0;
    dp[1] = 1;
    
    for i in 2..=n {
        dp[i] = dp[i-1] + dp[i-2];
    }
    dp[n]
}  

#[test] fn test_fib() { 
    //assert_eq!(fib_dp(0), 0);  // 边界测试
    assert_eq!(fib_dp(1), 1);
    assert_eq!(fib_dp(10), 55); 
    assert_eq!(fib_dp(20), 6765);
}  

// 添加性能对比演示
fn main() {
    use std::time::Instant;
    
    let test_cases = [10, 20, 30];
    for &n in &test_cases {
        let start = Instant::now();
        let result = fib_dp(n);
        let duration = start.elapsed();
        println!("fib({}) = {} 用时: {:?}", n, result, duration);
    }
    
    // 展示空间优化版本（可选）
    println!("\n空间优化版本结果:");
    println!("fib(30) = {}", fib_optimized(30));
}

// 空间优化版（O(1) 空间复杂度）
fn fib_optimized(n: u32) -> u32 {
    if n == 0 { return 0; }
    let (mut a, mut b) = (0, 1);
    for _ in 1..n {
        let c = a + b;
        a = b;
        b = c;
    }
    b
}